package com.xie.leetcode.string;

//409. 最长回文串
//        给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
//
//        在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
//
//        注意:
//        假设字符串的长度不会超过 1010。
//
//        示例 1:
//
//        输入:
//        "abccccdd"
//
//        输出:
//        7
//
//        解释:
//        我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

import java.util.HashMap;
import java.util.Map;

/**
 * @author xiezhendong
 * @date 2022/1/11
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        LongestPalindrome longestPalindrome = new LongestPalindrome();
        System.out.println(longestPalindrome.longestPalindrome("abccccdd"));
    }

    public int longestPalindrome(String s) {
        Map<String, Integer> charMap = new HashMap<>();

        for (char c : s.toCharArray()) {
            String str = String.valueOf(c);
            Integer count = charMap.get(str);
            if (count != null) {
                count++;
            } else {
                count = 1;
            }
            charMap.put(str, count);
        }

        int lastIndex = 0;
        int length = 0;
        for (Integer value : charMap.values()) {
            if (value % 2 == 0) {
                length = length + value;
            } else {
                if (lastIndex == 0) {
                    lastIndex = 1;
                }
            }
        }

        return length + lastIndex;
    }
}
